//
//  Problem875.swift
//  TestProject
//
//  Created by 武侠 on 2021/6/1.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 875. 爱吃香蕉的珂珂
 珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

 珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
 返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

 示例 1：
     输入: piles = [3,6,7,11], H = 8
     输出: 4
 示例 2：
     输入: piles = [30,11,23,4,20], H = 5
     输出: 30
 示例 3：
     输入: piles = [30,11,23,4,20], H = 6
     输出: 23
 提示：
     1 <= piles.length <= 10^4
     piles.length <= H <= 10^9
     1 <= piles[i] <= 10^9
 */
@objcMembers class Problem875: NSObject {
    func solution() {
//        print(minEatingSpeed([3,6,7,11], 8))
//        print(minEatingSpeed([30,11,23,4,20], 5))
//        print(minEatingSpeed([30,11,23,4,20], 6))
//
        print(minEatingSpeed([312884470], 968709470))
    }
    
    /*
     首先知道，每一堆最少要待1个小时，那么总共最少要待 piles.count个小时, 那么确保最大值也能1个小时吃完 piles.max / v = 1
     那么最长要待的时间呢？就是吃的很慢，在最少的那里就用了h个小时 piles.min / v = h
     满足条件的最小值
     
     */
    func minEatingSpeed(_ piles: [Int], _ h: Int) -> Int {
        if piles.count == 1 {
            return (piles[0] + h - 1) / h
        }
        var r = piles.max()!, l = piles.min()! / h
        var mid = 0, sum = 0
        while l < r {
            mid = l + (r - l) >> 1
            
            // 看看mid的速度，需要花费多长时间
            sum = 0
            for n in piles {
                sum += (n + mid - 1) / mid
            }
            if sum > h {        // 时间超了，不满足条件了, 速度有点慢，得快点
                l = mid + 1
            } else {
                r = mid
        
            }
        }
        
        return l
    }
}
